package com.love.labuladong;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author : zh
 * @Description :
 * @Date : 2024-05-15 09:51
 */
public class NSum {

    public static void main(String[] args) {
        int[] nums = {2,2,3,1,5,4,7,6,8,5,8};
//        List<int[]> res = twoSumTarget(nums, 10);
//        for (int[] re : res) {
//            System.out.println(Arrays.toString(re));
//        }

        List<List<Integer>> lists = threeSumTarget(nums, 0,11);
        for (List<Integer> list : lists) {
            System.out.println(Arrays.toString(list.toArray()));;
        }


    }


    /**
     * 两数之和
     * nums 数组中可能有多对元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿
     * 不能重复
     */
    public static List<int[]> twoSumTarget(int[] nums, int target){
        Arrays.sort(nums);
        int l = 0;
        int r = nums.length - 1;
        List<int[]> res = new ArrayList<>();
        while (l < r){
            int left = nums[l];
            int right = nums[r];
            int sum = left + right;
            if(sum > target){
                // r--;  优化点,假如有多个连续数字 [2,2,3,8,8]，但是结果是不允许重复的，所以可以跳过重复的
                while (l < r && nums[r] == right){
                    r--;
                }
            }else if(sum < target){
                //l++; 这里也是如此
                while (l < r && nums[l] == left ){
                    l++;
                }

            }else {
                res.add(new int[]{left,right});
                while (l < r && nums[l] == left){
                    l++;
                }
                while (l < r && nums[r] == right){
                    r--;
                }
            }

        }
        return res;
    }


    /**
     * 三数之和
     * 找 nums[] 中和为 target 的三元组，不允许重复
     * 思路：
     * 1. 穷举
     * 2.和为 target 的三个数字，nums 中 每一个元素 num[i] 都有可能
     * 3.确定一个数字之后，剩下的两个数字就是 target1 = target - nums[i]
     */
    public static List<List<Integer>> threeSumTarget(int[] nums,int start,int target){
        // 1.排序
        Arrays.sort(nums);
        int len = nums.length;
        // 2. 穷举 threeSum 的第一个数
        List<List<Integer>> res = new ArrayList<>();
        for (int i = start; i < len; i++) {
            // 3. 对 target - nums[i] 计算 twoSum
            List<List<Integer>> lists = twoSumTarget(nums, i + 1, target - nums[i]);
            // 4.如果存在满足条件的二元组，再加上 num[i] 就是结果三元组
            for (List<Integer> list : lists) {
                list.add(nums[i]);
                res.add(list);
            }
            // 5.跳过第一个数字重复的情况,否则会出现重复计算
            while (i < len -1 && nums[i] == nums[i + 1]){
                i++;
            }
        }
        return res;
    }


    public static List<List<Integer>> twoSumTarget(int[] nums,int start,int target){
        int l = start;
        int r = nums.length - 1;
        List<List<Integer>> res = new ArrayList<>();
        while (l < r){
            int left = nums[l];
            int right = nums[r];
            int sum = left + right;
            if(sum > target){
                // r--;  优化点,假如有多个连续数字 [2,2,3,8,8]，但是结果是不允许重复的，所以可以跳过重复的
                while (l < r && nums[r] == right){
                    r--;
                }
            }else if(sum < target){
                //l++; 这里也是如此
                while (l < r && nums[l] == left ){
                    l++;
                }
            }else {
                ArrayList<Integer> arr = new ArrayList<>();
                arr.add(left);
                arr.add(right);
                res.add(arr);
                while (l < r && nums[l] == left){
                    l++;
                }
                while (l < r && nums[r] == right){
                    r--;
                }
            }
        }
        return res;
    }


    /**
     * 如果 nSum 怎么办呢？
     *
     */





}
